/*
https://leetcode-cn.com/problems/number-of-music-playlists/solution/bo-fang-lie-biao-de-shu-liang-by-leetcode/
 */
public class Solution920 {
    public int numMusicPlaylists(int n, int goal, int k) {
        long[][] f=new long[goal+1][n+1];
        int m=1000000007;
        f[0][0]=1;
        for (int i=1;i<=goal;i++){
            for (int j=1;j<=n;j++){
                f[i][j]=(f[i][j]+(f[i-1][j-1])*(n-j+1)%m)%m;
                f[i][j]=(f[i][j]+(f[i-1][j])*(Math.max(0,j-k))%m)%m;
            }
        }
        return (int)f[goal][n];
    }

    public static void main(String[] args) {
        System.out.println(new Solution920().numMusicPlaylists(2,3,1));
    }
}
